package leetcode;

public class LeetCode61 {

    public static void main(String[] args) {
        LeetCode61 leetCode61 = new LeetCode61();
    }

    //双指针找到倒数k个节点
    public ListNode rotateRight1(ListNode head, int k) {
        ListNode oldTail = head, newHead = head, newTail = head;
//        while (k > 0) {
//            newTail = newTail.next;
//            k--;
//        }
        while (newTail.next != null) {
            oldTail = oldTail.next;
            newTail = newTail.next;
        }
        newHead = oldTail.next;
        oldTail.next = null;
        newTail.next = head;
        return newHead;
    }

    //先形成闭环
    public ListNode rotateRight2(ListNode head, int k) {
        ListNode tail = head, newTail = head, oldTail = head, newHead;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = head;
        while (k > 0) {
            newTail = newTail.next;
            k--;
        }
        while (newTail.next != null) {
            oldTail = oldTail.next;
            newTail = newTail.next;
        }
        newHead = oldTail.next;
        oldTail.next = null;
        newTail.next = head;
        return newHead;
    }
//------------------------------------------------------------------

    public ListNode rotateRight(ListNode head, int k) {
        // base cases
        if (head == null) return null;
        if (head.next == null) return head;

        // close the linked list into the ring
        ListNode old_tail = head;
        //链表长度
        int n;
        for (n = 1; old_tail.next != null; n++)
            old_tail = old_tail.next;
        old_tail.next = head;

        // find new tail : (n - k % n - 1)th node
        // and new head : (n - k % n)th node
        ListNode new_tail = head;
        for (int i = 0; i < n - k % n - 1; i++)
            new_tail = new_tail.next;
        ListNode new_head = new_tail.next;

        // break the ring
        new_tail.next = null;

        return new_head;
    }
}
